package liangtWorkSpace.sort;

/**
 * @ClassName BubbleSort
 * @Description : 功能说明
 * @Author : LiangT
 * @Date : 2020/4/16 11:04
 */

import java.util.Arrays;

/**
 * 冒泡排序算法
 */
public class BubbleSort {

    /**
     * 2020-08-25 看马士兵视频
     * 冒泡排序，大数下沉
     * @param arr
     */
    public static void sort(int arr[]){
        for (int i=0; i < arr.length;i++){
            for (int j = 0;j < arr.length-1-i;j++) {
                if (arr[j] < arr[j+1]){
                    SortUtils.swap(arr,j,j+1);
                }
            }
        }
        SortUtils.sout(arr);
    }

    /**
     * 比较前后值大小，如果前者比后者大则变更前后者的值
     * @param array
     */
    public static void bubbleSort(int array[]){
        for (int i = 0; i < array.length -1; i++){
            for (int j = 0; j < array.length -i-1; j++){
                int tmp = 0;
                if (array[j] > array[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }
    }

    /**
     * 优化1：排除部分无序操作
     * 比较前后值大小，如果前者比后者大则变更前后者的值
     * @param array
     */
    public static void bubbleSort1(int array[]){
        for (int i = 0; i < array.length -1; i++){
            boolean isSort = false;
            for (int j = 0; j < array.length -i-1; j++){
                int tmp = 0;
                if (array[j] > array[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    isSort = false;
                }
            }
            if (isSort){
                break;
            }
        }
    }

    /**
     * 优化2：设定有序-无序边界，排序算法只执行到有序无序的边界
     * 比较前后值大小，如果前者比后者大则变更前后者的值
     * @param array
     */
    public static void bubbleSort2(int array[]){
        int lastExchangeIndex = 0;
        int sortBorder = array.length -1;
        for (int i = 0; i < array.length -1; i++){
            boolean isSort = false;
            for (int j = 0; j < sortBorder; j++){
                int tmp = 0;
                if (array[j] > array[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    isSort = false;
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if (isSort){
                break;
            }
        }
    }
    /**
     * 优化2：双向排序，大的元素下沉，小的元素上升
     * 比较前后值大小，如果前者比后者大则变更前后者的值
     * @param array
     */
    public static void bubbleSort3(int array[]){
        for (int i = 0; i < array.length /2; i++){
            boolean isSort = false;
            for (int j = i; j < array.length -i - 1; j++){
                int tmp = 0;
                if (array[j] > array[j+1]){
                    tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                    isSort = false;
                }
            }
            for (int j = array.length -i- 1; j > i; j--){
                int tmp = 0;
                if (array[j] < array[j -1]){
                    tmp = array[j];
                    array[j] = array[j -1];
                    array[j -1] = tmp;
                    isSort = false;
                }
            }
            if (isSort){
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{5,8,4,2,3,1,6,8,9,0};
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
        array = new int[]{5,8,4,2,3,1,6,8,9,0};
        bubbleSort1(array);
        System.out.println(Arrays.toString(array));
        array = new int[]{5,8,4,2,3,1,6,8,9,0};
        bubbleSort2(array);
        System.out.println(Arrays.toString(array));
        array = new int[]{5,8,4,2,3,1,6,8,9,0};
        bubbleSort3(array);
        System.out.println(Arrays.toString(array));
        array = new int[]{5,8,4,2,3,1,6,8,9,0};
        sort(array);
    }
}
